/*
 *  Medieval Melee
 *  Copyright (C) 2009 Ben Foote
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *  Uzebox is a reserved trade mark
*/

#include "AI.h"
#include "logic.h"
#include "q.h"

#ifndef UNIT_TEST
    #include <uzebox.h>
    #include <avr/pgmspace.h>
#endif

#ifdef UNIT_TEST
	#include "unit_test.h"
#endif

/// A type definition that is only useful to our AI functions that define how
/// the AI moves the cursor and pieces around.
typedef enum
{
    LEFT = 0,
    RIGHT,
    UP,
    DOWN,
    SWAP   
}MOVE_TYPE;

/// This enumerates all the possible states the AI could be in, according
/// to the finite state machine defined for the AI process.
enum AI_STATE
{
    IDLE = 0,
    HORIZONTALMATCH,
    VERTICALMATCH,
    RANDOMMOVE,
    MAKEMOVES,
    NUM_STATES
};

/// Globals for our AI functions.
unsigned char ucQStore[MAX_Q_SIZE];
QUEUE_TYPE objQueue;
enum AI_STATE eAIState;

/// Local function definitions.
bool AIi_CheckHorizontalMatches(PLAYFIELD_TYPE *tPlayfield, CURSOR_POS *tCurs);
bool AIi_CheckVerticalMatches(PLAYFIELD_TYPE *tPlayfield, CURSOR_POS *tCurs);
bool AIi_MakeMoves(PLAYFIELD_TYPE *tPlayfield, CURSOR_POS *tCurs);
bool AIi_RowFull(const PLAYFIELD_TYPE *tPlayfield, unsigned char ucRow);
unsigned char AIi_RowContains(const PLAYFIELD_TYPE *tPlayfield, unsigned char ucRow, unsigned char ucType);

void MoveToColumn(unsigned char ucCurrentColumn, unsigned char ucDesiredColumn);
void MoveToRow(unsigned char ucCurrentRow, unsigned char ucDesiredRow);
void MoveBlockLeft(unsigned char ucMoves, unsigned char ucCursXpos);
void MoveBlockRight(unsigned char ucMoves, unsigned char ucCursXpos);

unsigned char FindNextInRow(PLAYFIELD_TYPE *tPlayfield, unsigned char ucCurrentCol, unsigned char ucRow, unsigned char ucType);


///////////////////////////////////////////////////////////////////////////////
/// Initializes the Queue and state for our AI functions.
///////////////////////////////////////////////////////////////////////////////
void AI_Init(void)
{
    Q_Init(&objQueue, ucQStore);
    eAIState = IDLE;
}


///////////////////////////////////////////////////////////////////////////////
/// Beginning of CPU AI.
///////////////////////////////////////////////////////////////////////////////
unsigned char AI_Think(PLAYFIELD_TYPE *tPlayfield, CURSOR_POS *tCurs)
{
    static unsigned char ucMoves = 0;
    
    switch(eAIState)
    {
        case IDLE:
            Print(2,2, PSTR("IDLE"));                            
            eAIState = VERTICALMATCH;
            break;
            
        case HORIZONTALMATCH:
            Print(2,2, PSTR("HORZ"));                            
            if(AIi_CheckHorizontalMatches(tPlayfield, tCurs) == true)
                eAIState = MAKEMOVES;
            else
                eAIState = VERTICALMATCH;
            break;
            
        case VERTICALMATCH:
            Print(2,2, PSTR("VERT"));                            
            if(AIi_CheckVerticalMatches(tPlayfield, tCurs) == true)
                eAIState = MAKEMOVES;
            else
                eAIState = IDLE;
            break;
            
        case RANDOMMOVE:
            Print(2,2, PSTR("RAND"));
            break;
            
        case MAKEMOVES:
            Print(2,2, PSTR("MOVE"));        
            if(AIi_MakeMoves(tPlayfield, tCurs) == false)
                eAIState = IDLE;
            break;
            
        default:
            break;
    }
    
    return ++ucMoves; 
}


///////////////////////////////////////////////////////////////////////////////
/// This function simply looks at a row and returns true if each spot in the
/// row contains a block.
///////////////////////////////////////////////////////////////////////////////
bool AIi_RowFull(const PLAYFIELD_TYPE *tPlayfield, unsigned char ucRow)
{
    bool bFull = true;
    
    if(ucRow > 11)
        return false;
    
    for(unsigned char i=0; i<6; i++)
    {
        if(tPlayfield->tField[i][ucRow].ucBlock == 0)
            bFull = false;
    }    
    
    return bFull;
}


///////////////////////////////////////////////////////////////////////////////
/// Returns the number of blocks of the specified type in the specified row.
///////////////////////////////////////////////////////////////////////////////
unsigned char AIi_RowContains(const PLAYFIELD_TYPE *tPlayfield, unsigned char ucRow, unsigned char ucType)
{
    unsigned char ucCount = 0;
    
    if(ucRow > 11U)
        return 0;
    
    for(unsigned char i = 0U; i < 6U; i++)
    {
        if(tPlayfield->tField[i][ucRow].ucBlock == ucType)
            ucCount++;
    }
    
    return ucCount;
}


///////////////////////////////////////////////////////////////////////////////
/// Looks at the current playfield in an attempt to find if there are any
/// matches to be made in any row, and if there are, builds a move list
/// that would complete the match.
///////////////////////////////////////////////////////////////////////////////
bool AIi_CheckHorizontalMatches(PLAYFIELD_TYPE *tPlayfield, CURSOR_POS *tCurs)
{   
    bool bMatch = false;
    unsigned char ucRowFound = 0U;
    unsigned char ucTypeFound = 0U;
    
    /// First loop through all of the rows, starting at the bottom to see if its full.
    for(unsigned char ucRowNum=11U; ucRowNum > 0U; ucRowNum--)
    {
        if(AIi_RowFull(tPlayfield, ucRowNum) == true)
        {   /// If a row is full, check to see if it has 3 or more of one type in it.
            for(unsigned char ucType=1; ucType <= 6U; ucType++)
            {
                if(AIi_RowContains(tPlayfield, ucRowNum, ucType) > 2U)
                {
                    bMatch = true;
                    ucRowFound = ucRowNum;
                    ucTypeFound = ucType;
                    break; /// Break out if we've found a full row that has a match.
                }
            }
        }
        
        /// Break out of our search if we've found a row that has a match.
        if(bMatch == true)
            break;
    }
    
    /// We've found a match, now build the list of moves required to make it.
    if(bMatch == true)        
    {   
        unsigned char ucNumInLine = 1U;/// We have 1 in a row to begin with.
        unsigned char ucNext = 0U;	  /// This is the column position of the next block of the 
        							  /// same type. Initialize to 0.
        unsigned char ucTxCurs = 0U;   /// Temporary variable telling us where the x cursor
                                      /// position is/will be.                                      
        unsigned char ucCol = 0U;
        
                
        /// Find the first instance of the type of block that we've matched.
        ucCol = FindNextInRow(tPlayfield, 0U, ucRowFound, ucTypeFound);
        /// Then find the next position of the same type of block.
        ucNext = FindNextInRow(tPlayfield, ucCol+1U, ucRowFound, ucTypeFound);
        
        /// Now move the cursor to our current row, and the column of the first match.
        MoveToRow(tCurs->ucYpos, ucRowFound);
        MoveToColumn(tCurs->ucXpos, ucCol);
        
        /// Mark the temporary cursor position as having moved to ucCol.
        ucTxCurs = ucCol;                
        
        while(ucNumInLine < 3U)
        {   /// If our current column and next are next to eachother, then move to
	    	/// the next in line and increment our number of blocks in line.
            if((ucNext - ucCol) == 1U)
            {
                ucCol = ucNext;
                ucNext = FindNextInRow(tPlayfield, ucCol+1U, ucRowFound, ucTypeFound);
                ucNumInLine++;
            }
            else
            {/// Otherwise, we need to move over and move the block back.
                MoveToColumn(ucTxCurs, (ucNext-1U));
                ucTxCurs = ucNext - 1U;
                MoveBlockLeft(ucNext - ucCol - 1U, ucTxCurs);
                ucTxCurs = ucTxCurs - (ucNext - ucCol - 1U);
                
                ucNumInLine++;
                
                ucCol++;
                ucNext = FindNextInRow(tPlayfield, ucNext+1U, ucRowFound, ucTypeFound);
            }
        }
    }
    
	/// Return whether we've matched or not.
    return bMatch;
}


///////////////////////////////////////////////////////////////////////////////
/// Looks at the current playfield in an attempt to find if there are any
/// vertical matches to be made in any column, and if there are, builds a move
/// list that would complete the match.
///////////////////////////////////////////////////////////////////////////////
bool AIi_CheckVerticalMatches(PLAYFIELD_TYPE *tPlayfield, CURSOR_POS *tCurs)
{
    bool          bMatch      = false;
    unsigned char ucRowFound  = 0U;
    unsigned char ucTypeFound = 0U;
    unsigned char ucNumFound  = 0U;
    
    /// First look at all the possible block types in order...
    for(unsigned char ucType = 1U; ucType <= 6U; ucType++)
    {/// ...in each row , starting at the bottom, to see which type has the 
     /// most vertical matches.
        for(unsigned char ucRowNum = 11U; ucRowNum > 0U; ucRowNum--)
        {   /// In order to be part of a match, the row has to be full, or
            /// the row below the one we're looking at has to be full so that
            /// we know that we can move the block in question.
            if((AIi_RowFull(tPlayfield, ucRowNum) == true) ||
			   ((ucRowNum >= 1U) && (AIi_RowFull(tPlayfield, ucRowNum-1U) == true)))
            {
                /// Check to see if the current row contains a block of ucType.
                if(AIi_RowContains(tPlayfield, ucRowNum, ucType) >= 1U)
                {                
                    ucNumFound++;
                    
                    /// If we have 3 blocks that can be put in line in a column
                    /// then mark it, and bail out of the search.
                    if(ucNumFound == 3U)
                    {
                        ucRowFound  = ucRowNum;
                        ucTypeFound = ucType;
                        bMatch = true;
                        break;
                    }
                }
                else
                {   /// If we haven't found 3 in a row, and we find a row
                    /// that doesn't have a block of ucType in it, then 
                    /// restart the count.
                    ucNumFound = 0;
                }
                
                /// We found a match, bail out of the search.
                if(bMatch == true)
                    break;
            }
        }
        
        if(bMatch == true)
            break;
    }
    
    /// Build our moves list to make the moves that match the blocks we've
    /// found.
    if(bMatch == true)
    {
        unsigned char ucNumInLine = 1U;/// We have 1 in a column to begin with.
        unsigned char ucNextCol   = 0U;/// This is the column position of the next block of the 
        							   /// same type. Initialize to 0.
        unsigned char ucTxCurs = 0U;   /// Temporary variable telling us where the x cursor
                                       /// position is/will be.
        unsigned char ucCol    = 0U;   /// This stores the current column we're in.
        
        /// Find the first column of the type of block that we've matched.
        ucCol		= FindNextInRow(tPlayfield, 0U, ucRowFound-ucNumFound-1U, ucTypeFound);
        /// Then find the next column of the same type of block.
        ucNextCol	= FindNextInRow(tPlayfield, 0U, ucRowFound-ucNumFound-2U, ucTypeFound);
        
        /// Now move the cursor to our current row, and the column of the first match.
        MoveToRow(tCurs->ucYpos, ucRowFound-1U);
        MoveToColumn(tCurs->ucXpos, ucNextCol);
        
        /// Mark the temporary cursor position as having moved to ucNextCol.
        ucTxCurs = ucNextCol;
        
        /// Now, while we still don't have 3 blocks in a vertical line,
        /// find matches until we do.        
        while(ucNumInLine < 3U)
        {   /// If our current column and next column match, then increment
            /// our number of blocks in line that match.
            if(ucNextCol == ucCol)
            {/// If our two blocks align vertically, move up one row, and 
                /// find the next column in the next row, then move there.
                MoveToRow(ucRowFound-2U+ucNumInLine, ucRowFound-1U+ucNumInLine);
                ucNextCol = FindNextInRow(tPlayfield, 0U, ucRowFound-1U+ucNumInLine, ucTypeFound);
                MoveToColumn(ucTxCurs, ucNextCol);
                ucTxCurs = ucNextCol;
                ucNumInLine++;                                
            }
            else
            {/// Now move our block left or right the correct number of spaces.
                if(ucNextCol > ucCol)
                {
                    MoveBlockLeft(ucNextCol - ucCol, ucTxCurs);                    
                }
                else
                {
                    MoveBlockRight(ucCol - ucNextCol, ucTxCurs);
                }
                
                /// Now update our cursor and column positions.
                ucTxCurs = ucCol;
                ucNextCol = ucCol;                                                                
            }
        }
    }
    
    /// Return whether we've matched or not.
    return bMatch;
}


///////////////////////////////////////////////////////////////////////////////
/// If there are any moves in the move queue, this function will make them,
/// one by one until there aren't any more to be made.
///////////////////////////////////////////////////////////////////////////////
bool AIi_MakeMoves(PLAYFIELD_TYPE *tPlayfield, CURSOR_POS *tCurs)
{
    MOVE_TYPE myMove;
    
    if(Q_IsEmpty(&objQueue, ucQStore) == false)
    {
        myMove = (MOVE_TYPE)Q_Dequeue(&objQueue, ucQStore);
        
        switch(myMove)
        {
            case LEFT:
                Print(2,3, PSTR("LEFT "));
                if(tCurs->ucXpos > 0)
                    tCurs->ucXpos--;
                break;
            
            case RIGHT:
                Print(2,3, PSTR("RIGHT"));            
                if(tCurs->ucXpos < 4)
                    tCurs->ucXpos++;
                break;
                
            case DOWN:
                Print(2,3, PSTR("DOWN "));            
                if(tCurs->ucYpos < 11)
                    tCurs->ucYpos++;
                break;
                
            case UP:
                Print(2,3, PSTR("UP   "));            
                if(tCurs->ucYpos > 0)
                    tCurs->ucYpos--;
                break;
            
            case SWAP:
                Print(2,3, PSTR("SWAP "));                
                LGC_SwapBlock(tPlayfield, tCurs->ucXpos, tCurs->ucYpos);
                break;
                
            default:
                return false;
                break;
        }
        
        return true;
    }
    
    return false;
}


///////////////////////////////////////////////////////////////////////////////
/// This is a utility function that will move the cursor from the current
/// column to the desired column by enqueing the appropriate number
/// of left or right moves, with boundary checking.
///////////////////////////////////////////////////////////////////////////////
void MoveToColumn(unsigned char ucCurrentColumn, unsigned char ucDesiredColumn)
{
    MOVE_TYPE myMove;
    
    if((ucCurrentColumn > 4) || (ucDesiredColumn > 4))
        return;
    
    if(ucCurrentColumn < ucDesiredColumn)
    {
        for(unsigned char i = ucCurrentColumn; i < ucDesiredColumn; i++)
        {
            myMove = RIGHT;
            Q_Enqueue(&objQueue, ucQStore, (unsigned char)myMove);            
        }
    }
    else
    {
        if(ucCurrentColumn > ucDesiredColumn)
        {
            for(unsigned char i = ucCurrentColumn; i > ucDesiredColumn; i--)
            {
                myMove = LEFT;
                Q_Enqueue(&objQueue, ucQStore, (unsigned char)myMove);            
            }
        }
    }
}


///////////////////////////////////////////////////////////////////////////////
/// This is a utility function that will move the cursor from the current
/// row to the desired row by enqueing the appropriate number
/// of up or down moves, with boundary checking.
///////////////////////////////////////////////////////////////////////////////
void MoveToRow(unsigned char ucCurrentRow, unsigned char ucDesiredRow)
{    
    MOVE_TYPE myMove;
    
    if((ucCurrentRow > 11) || (ucDesiredRow > 11))
        return;
    
    if(ucCurrentRow < ucDesiredRow)
    {
        for(unsigned char i = ucCurrentRow; i < ucDesiredRow; i++)
        {
            myMove = DOWN;
            Q_Enqueue(&objQueue, ucQStore, (unsigned char)myMove);
        }
    }
    else        
    {
        if(ucCurrentRow > ucDesiredRow)
        {
            for(unsigned char i = ucCurrentRow; i > ucDesiredRow; i--)
            {
                myMove = UP;
                Q_Enqueue(&objQueue, ucQStore, (unsigned char)myMove);
            }                
        }
    }
}


///////////////////////////////////////////////////////////////////////////////
/// Enqueus the moves to swap the current block, and then moves the cursor
/// left one block.
///////////////////////////////////////////////////////////////////////////////
void MoveBlockLeft(unsigned char ucMoves, unsigned char ucCursXpos)
{
    for(unsigned char i = 0; i < ucMoves; i++)
    {
        Q_Enqueue(&objQueue, ucQStore, (unsigned char)SWAP);
        MoveToColumn(ucCursXpos, ucCursXpos - 1);
        ucCursXpos--;
    }
}


///////////////////////////////////////////////////////////////////////////////
/// Enqueus the moves to swap the current block, and then moves the cursor
/// right one block.
///////////////////////////////////////////////////////////////////////////////
void MoveBlockRight(unsigned char ucMoves, unsigned char ucCursXpos)
{
    for(unsigned char i = 0; i < ucMoves; i++)
    {
        Q_Enqueue(&objQueue, ucQStore, (unsigned char)SWAP);
        MoveToColumn(ucCursXpos, ucCursXpos + 1);
        ucCursXpos++;
    }
}

///////////////////////////////////////////////////////////////////////////////
/// Finds the next block of the given type at the current row, and returns its
/// column number if its found.
///////////////////////////////////////////////////////////////////////////////
unsigned char FindNextInRow(PLAYFIELD_TYPE *tPlayfield, unsigned char ucCurrentCol, unsigned char ucRow, unsigned char ucType)
{   /// Start looking at the block to the right of our current column.
    for(unsigned int i = ucCurrentCol; i < 6; i++)
    {   /// If we find a match, return its column number.
        if(tPlayfield->tField[i][ucRow].ucBlock == ucType)
            return i;
    }
    
    /// Otherwise, just return 0 to be safe.
    return 0;    
}
